package com.sunny.l56;

import java.util.ArrayList;

/**
 * @Author zsunny
 * @Date 2018/9/13 11:06
 * @Mail zsunny@yeah.net
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String str = "19216811";
        ArrayList<String> l = new ArrayList<>();
        solution.dfs(l, str);
        System.out.println(solution.res);
    }

    private ArrayList<ArrayList<String>> res = new ArrayList<>();
    public ArrayList<String> restoreIpAddresses(String s) {
        ArrayList<String> ret = new ArrayList<>();
        if(null == s || s.length() < 4){
            return ret;
        }
        ArrayList<String> list = new ArrayList<>();
        dfs(list, s);
        res.forEach(list1 -> {
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<list1.size();i++){
                sb.append(list1.get(i));
                if(i != list1.size()-1){
                    sb.append(".");
                }
            }
            ret.add(sb.toString());
        });
        return ret;
    }
    public void dfs(ArrayList<String> list, String str){
        if(4 == list.size()){
            if("".equals(str)){
                ArrayList<String> tmpList = new ArrayList<>(list);
                res.add(tmpList);
            }
            return;
        }
        int len = str.length();
        for(int j=1;j<=Integer.min(len, 3);j++){
            if(j>1 && str.charAt(0) == '0'){
                break;
            }
            if(j==3 && (str.charAt(0) > '2' ||
                    (str.charAt(0) == '2' && str.charAt(1) > '5') ||
                    (str.charAt(0) == '2' && str.charAt(1)=='5' && str.charAt(2)>'5'))){
                break;
            }
//            System.out.println(j+" "+str.substring(0, j)+" "+str.substring(j) + " "+list);
            list.add(str.substring(0, j));
            dfs(list, str.substring(j));
            list.remove(list.size()-1);
        }
    }
}
